#include<vector>
#include<string>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Codec {
private:
    TreeNode* deserialize(const string& data, int& index) {
        int begin = index;
        while (index < data.length() && data[index] != ',')
            ++index;
        if (index == begin) {
            ++index;
            return NULL;
        }
        int val = atoi(data.substr(begin, index - begin).c_str());
        TreeNode* root = new TreeNode(val);
        ++index;
        root->left = deserialize(data, index);
        root->right = deserialize(data, index);
        return root;
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL) return "";
        string res = "";
        res += to_string(root->val) + ",";
        res += serialize(root->left) + ",";
        res += serialize(root->right);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "") return NULL;
        int index = 0;
        return deserialize(data, index);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

int main() {
    Codec codec;
    TreeNode* root = new TreeNode(1);
    TreeNode* left = new TreeNode(2);
    TreeNode* right = new TreeNode(3);
    right->left = new TreeNode(4);
    right->right = new TreeNode(5);
    root->left = left;
    root->right = right;
    string str=codec.serialize(root);
    auto res = codec.deserialize(str);
}